package huawei.js2025;

import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 亲子游戏
 * 广度优先搜索
 */
public class Question49 {

    static int[][] d = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int candySum(int[][] path, int N) {
        Queue<StepInfo> waitVisit = new LinkedList<>();

        for (int i = 0; i < path.length; i++) {
            for (int j = 0; j < path[i].length; j++) {
                if (path[i][j] == -3) {
                    waitVisit.offer(new StepInfo(i, j, 0, 0));
                }
            }
        }

        int currentStep = Integer.MAX_VALUE;
        int currentMaxCandy = 0;

        int[][] visited = new int[N][N];

        while (!waitVisit.isEmpty()) {
            StepInfo info = waitVisit.poll();
            int x = info.x, y = info.y;
            visited[x][y] = 1;

            for (int[] d : d) {
                int x1 = x + d[0], y1 = y + d[1];
                if (x1 >= 0 && x1 < N && y1 >= 0 && y1 < N && visited[x1][y1] == 0) {
                    if (path[x1][y1] == -1) continue;
                    if (path[x1][y1] == -2) {
                        if (info.steps <= currentStep) {
                            currentStep = info.steps;
                            currentMaxCandy = Math.max(currentMaxCandy, info.candySum);
                        }
                    } else {
                        waitVisit.add(new StepInfo(x1, y1, info.steps + 1, info.candySum + path[x1][y1]));
                    }
                }
            }

        }

        return currentMaxCandy;
    }

    public static class StepInfo{
        int x;
        int y;
        int steps;
        int candySum;

        public StepInfo(int x, int y, int steps, int candySum) {
            this.x = x;
            this.y = y;
            this.steps = steps;
            this.candySum = candySum;
        }
    }

    public static void main(String[] args) {
//        int[][] ints = new int[][]{
//                {3,2,1,-3},
//                {1,-1,1,1},
//                {1,1,-1,2},
//                {-2,1,2,3}
//        };

        int[][] ints = new int[][]{
                {3,2,1,-3},
                {-1,-1,1,1},
                {1,1,-1,2},
                {-2,1,-1,3}
        };

        Question49 q = new Question49();
        System.out.println(q.candySum(ints, 4));
    }


}
